import collections


# 单向搜索
# class Solution(object):
#     def subarraySum(self, nums, k):
#         """
#         :type nums: List[int]
#         :type k: int
#         :rtype: int
#         """
#         ans = 0
#         prefix = collections.defaultdict(int)
#         for item in nums:
#             new_prefix = collections.defaultdict(int)
#             new_prefix[item] += 1
#             for key in prefix:
#                 new_prefix[item + key] += prefix[key]
#             if k in new_prefix:
#                 ans += new_prefix[k]
#             prefix = new_prefix
#         return ans

# 双向搜索
# class Solution(object):
#     def subarraySum(self, nums, k):
#         """
#         :type nums: List[int]
#         :type k: int
#         :rtype: int
#         """
#         ans = 0
#         prefix1 = collections.defaultdict(int)
#         n = len(nums)
#         mid = n // 2
#         for i in range(mid):
#             new_prefix = collections.defaultdict(int)
#             new_prefix[nums[i]] += 1
#             for key in prefix1:
#                 new_prefix[nums[i] + key] += prefix1[key]
#             if k in new_prefix:
#                 ans += new_prefix[k]
#             prefix1 = new_prefix
#         prefix2 = collections.defaultdict(int)
#         for i in range(n - 1, mid - 1, -1):
#             new_prefix = collections.defaultdict(int)
#             new_prefix[nums[i]] += 1
#             for key in prefix2:
#                 new_prefix[nums[i] + key] += prefix2[key]
#             if k in new_prefix:
#                 ans += new_prefix[k]
#             prefix2 = new_prefix
#         for key in prefix1:
#             if k - key in prefix2:
#                 ans += prefix1[key] * prefix2[k - key]
#         return ans

# 前缀和
class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        prefix = collections.defaultdict(int)
        total = 0
        ans = 0
        prefix[0] = 1
        for item in nums:
            total += item
            ans += prefix[total - k]
            prefix[total] += 1
        return ans


data = Solution()
# nums = [1, 2, 3]
# k = 3
# print(data.subarraySum(nums, k))
nums = [100, 1, 2, 3, 4]
k = 6
print(data.subarraySum(nums, k))
# nums = [1, 1, 1]
# k = 2
# print(data.subarraySum(nums, k))
# nums = [-1, -1, 1]
# k = 1
# print(data.subarraySum(nums, k))
# nums = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
# k = 0
# print(data.subarraySum(nums, k))
nums = [1, 2, 1, 2, 1]
k = 3
print(data.subarraySum(nums, k))
